import math


class Solution:
    _MOD = 10 ** 9 + 7

    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        # 求a和b的最小公倍数：a和b的最小公倍数=a*b/a和b的最大公因数
        v = int(a * b / math.gcd(a, b))

        # a和b的最小公倍数中包含多少个神奇数字
        k = v // a + v // b - 1

        c, d = divmod(n, k)

        # 计算结果包含完整的公倍数的数量的值
        ans = c * v

        # 计算不足一个完整公倍数时的值
        l, r = 0, v - 1
        while l < r:
            m = (l + r) // 2
            if m // a + m // b >= d:
                r = m
            else:
                l = m + 1
        return (ans + l) % self._MOD


if __name__ == "__main__":
    print(Solution().nthMagicalNumber(1, 2, 3))  # 2
    print(Solution().nthMagicalNumber(4, 2, 3))  # 6
    print(Solution().nthMagicalNumber(5, 2, 4))  # 10
    print(Solution().nthMagicalNumber(3, 6, 4))  # 8
